/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/
/**
 * \file
 * \brief Search structure for locating entries by ID - implementation.
 * \author Antti Maula <antti.maula@tkk.fi>
 *
 * See Detailed description from the 'idmap.h' file.
 */
//*****************************************************************************
#include "idmap.h"
#include "owndebug.h"
#include <stdlib.h> // malloc
#include <string.h> // memset


// This module is currently well tested, hence no asserts are defined.
#define NDEBUG
#include <assert.h>


//*****************************************************************************
inline static TIDMapEntryBin *idMapFindBin(const TIDMap *im, const unsigned int aKey);
static void idMapInitBinArray(TIDMap *im, 
                              const unsigned int aBinCount);
static void idMapBinInit(TIDMapEntryBin *imeb);
static int idMapBinAddEntry(TIDMapEntryBin *imeb, const unsigned int aKey, void *aData);
static int idMapBinDeleteEntry(TIDMapEntryBin *imeb, const unsigned int aKey);
static TIDMapEntry *idMapBinFindEntry(TIDMapEntryBin *imeb, const unsigned int aKey);
inline static unsigned int idMapGetBinIndexByKey(const TIDMap *im, const unsigned int aKey);
inline static TIDMapEntry *idMapEntryCreateAndInit(const unsigned int nodeID,
                                                   void *entry,
                                                   struct _idmap_entry *prev,
                                                   struct _idmap_entry *next);
inline static void idMapEntryDestroy(TIDMapEntry *ime);
//*****************************************************************************
//*****************************************************************************

TIDMap *idMapCreate()
{
  return (TIDMap *)malloc( sizeof(TIDMap) );
}
//*****************************************************************************

int idMapInit( TIDMap *im, 
               const unsigned int aHashBinCount)
{
  int result = -1;
  assert(im != NULL);
  assert(aHashBinCount > 0);
  
  ///// Init contents to zero.
  memset(im, 0x00, sizeof(TIDMap));

  ///// Init Map structures.
  idMapInitBinArray(im, aHashBinCount);

  // Done!
  result = 0;

  return result;
}
//*****************************************************************************

void idMapDeinit( TIDMap *im )
{
  int i;
  assert(im != NULL);
  
  for(i=0; i < im->hashBinCount; ++i) {
    // Take bin pointer
    TIDMapEntryBin *bin = &im->idMapEntryBins[i];

    // Take pointer to first element in bin.
    TIDMapEntry *e = bin->first;
    
    // Destroy elements in bin.
    while(e) {
      TIDMapEntry *del = e;
      e = e->next;
      idMapEntryDestroy(del);
    }
  }

  // Destroy bin array.
  free(im->idMapEntryBins);
  im->idMapEntryBins = NULL;
}
//*****************************************************************************

void idMapDestroy( TIDMap *im )
{
  assert(im != NULL);
  free(im);
}
//*****************************************************************************

void idMapClear(TIDMap *im)
{
  int i;
  for(i=0; i < im->hashBinCount; ++i) {
    TIDMapEntryBin *bin = &im->idMapEntryBins[i];
    TIDMapEntry *e = bin->first;
    
    // Clear bin. (first entry pointer is stored before above)
    bin->first = NULL;
    bin->entryCount = 0;

    // Destroy elements.
    while(e) {
      TIDMapEntry *del = e;
      idMapEntryDestroy(del);
      e = e->next;
    }
  }
  im->total_elements = 0;
}
//*****************************************************************************

int idMapAddEntry(TIDMap *im, const unsigned int aNodeID, void *aEntry)
{
  int result = -1;
  assert(im != NULL);

  // Get correct Bin.
  TIDMapEntryBin *b = idMapFindBin(im, aNodeID);
  assert(b != NULL);

  // Add to bin.
  result = idMapBinAddEntry(b, aNodeID, aEntry);

  // Update counter
  if (!result) ++im->total_elements;

  return result;
}
//*****************************************************************************

int idMapDeleteEntry(TIDMap *im, const unsigned int aNodeID)
{ 
  int result = -1;
  assert(im != NULL);

  // Get correct Bin.
  TIDMapEntryBin *b = idMapFindBin(im, aNodeID);
  assert(b != NULL);
  
  // Add to bin.
  result = idMapBinDeleteEntry(b, aNodeID);

  // Update counter
  if (!result) --im->total_elements;

  return result;
}
//*****************************************************************************

const TIDMapEntry *idMapGetEntry(const TIDMap *im, const unsigned int aNodeID)
{ 
  assert(im != NULL);

  // Get correct Bin.
  TIDMapEntryBin *b = idMapFindBin(im, aNodeID);
  assert(b != NULL);
  
  // Add to bin.
  return idMapBinFindEntry(b, aNodeID);
}
//*****************************************************************************

void idMapGetNextEntryIterator(const TIDMap *im, TIDMapEntryIterator *aIter)
{
  assert(im != NULL);
  assert(aIter != NULL);
  
  aIter->bin = 0;
  const TIDMapEntryBin *b = &im->idMapEntryBins[0];
  aIter->entry = b->first;
}
//*****************************************************************************

const TIDMapEntry *idMapGetNextEntry(const TIDMap *im, TIDMapEntryIterator *aIter)
{
  const TIDMapEntry *e = NULL;
  assert(im != NULL);
  assert(aIter != NULL);

  if (aIter->entry) {
    e = aIter->entry;
    aIter->entry = e->next;

  } else {
    aIter->bin++;
    if (aIter->bin < im->hashBinCount) {
      const TIDMapEntryBin *b = &im->idMapEntryBins[aIter->bin];
      if (b->first != NULL) {
        e = b->first;
        aIter->entry = b->first->next;

      } else {
        e = idMapGetNextEntry(im, aIter);

      }
    } 
  }

  return e;
}
//*****************************************************************************

inline unsigned long int idMapGetTotalElementCount(const TIDMap *im)
{
  return im->total_elements;
}
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************

inline static TIDMapEntryBin *idMapFindBin(const TIDMap *im, const unsigned int aKey)
{
  return &im->idMapEntryBins[idMapGetBinIndexByKey(im, aKey)];
}
//*****************************************************************************

inline static void idMapEntryDestroy(TIDMapEntry *ime)
{
  free(ime);
}
//*****************************************************************************

inline static unsigned int idMapGetBinIndexByKey(const TIDMap *im, const unsigned int aKey)
{
  assert(im != NULL);
  assert(im->hashBinCount > 0);
  return (aKey % im->hashBinCount);
}
//*****************************************************************************

static void idMapInitBinArray(TIDMap *im, 
                              const unsigned int aBinCount)
{
  int i;
  assert(im->idMapEntryBins == NULL);
  assert(aBinCount > 0);

  // Allocate bins.
  im->hashBinCount = aBinCount;
  im->idMapEntryBins = (TIDMapEntryBin *)malloc( sizeof(TIDMapEntryBin) * im->hashBinCount );
  assert(im->idMapEntryBins != NULL);

  dPrint(ODDEBUG(0),"idMap %p: Reserved %lu bytes for the Hash table", 
         im, (long unsigned)(sizeof(TIDMapEntryBin) * im->hashBinCount));
  
  // Initialize bins.
  for(i=0; i < aBinCount; ++i) {
    idMapBinInit(&im->idMapEntryBins[i]);
  }
}
//*****************************************************************************

inline static TIDMapEntry *idMapEntryCreateAndInit(const unsigned int nodeID,
                                                   void *entry,
                                                   struct _idmap_entry *prev,
                                                   struct _idmap_entry *next)
{
  TIDMapEntry *ime = (TIDMapEntry *)malloc(sizeof(TIDMapEntry));
  assert(ime != NULL);
  ime->nodeID = nodeID;
  ime->entry = entry;
  ime->prev = prev;
  ime->next = next;
  return ime;
}
//*****************************************************************************

static void idMapBinInit(TIDMapEntryBin *imeb)
{
  // Zero entries, 1 reserved (initial, allows realloc by
  // idMapResizeBin())
  imeb->entryCount = 0;

  // Mark empty.
  imeb->first = NULL;
}
//*****************************************************************************

static int idMapBinAddEntry(TIDMapEntryBin *imeb, const unsigned int aKey, void *aData)
{
  int result = -1;

  // Create new entry.
  TIDMapEntry *newentry = idMapEntryCreateAndInit(aKey, aData, NULL, NULL);

  assert(imeb != NULL);

  // Take first entry.
  TIDMapEntry *e = imeb->first;
  
  if (!e) {
    imeb->first = newentry;
    result = 0;

  } else {

    while(e) {
      if (e->nodeID == aKey) {
        // Exact match found. Failure.
        idMapEntryDestroy(newentry);
        //        result = 0;
        break;

      } else if (e->nodeID > aKey) {
        // We passed the point where the key can exist, so insert before this.
        newentry->next = e;
        newentry->prev = e->prev;
        if (e->prev) {
          e->prev->next = newentry;
        } else {
          imeb->first = newentry; 
        }
        e->prev = newentry;
        result = 0;
        break;

      } else if (e->next == NULL) {
        // This was the last entry.
        e->next = newentry;
        newentry->prev = e;
        result = 0;
        break;
        
      }
      e = e->next;
    }

  }

  ++imeb->entryCount;

  return result;
}
//*****************************************************************************

static int idMapBinDeleteEntry(TIDMapEntryBin *imeb, const unsigned int aKey)
{
  int result = -1;

  TIDMapEntry *e = idMapBinFindEntry(imeb, aKey);
  if (e) {

    // Remove entry from chain.
    if (e->prev) {
      // Previous exists, so marks its next as deleted items next.
      e->prev->next = e->next;
      if (e->next) e->next->prev = e->prev;

    } else {
      // Previous doesn't exist, so mark first element as deleted
      // items next.
      imeb->first = e->next;
      if (e->next) e->next->prev = NULL;
    }

    // Delete allocated entry
    idMapEntryDestroy(e);

    // Update stats.
    imeb->entryCount --;

    // update result
    result = 0;
  }

  return result;
}
//*****************************************************************************

static TIDMapEntry *idMapBinFindEntry(TIDMapEntryBin *imeb, 
                                      const unsigned int aKey)
{
  TIDMapEntry *f = imeb->first;
  while(f) {
    if (f->nodeID == aKey) {
      // Node was found.
      return f;
      
    } else if (f->nodeID > aKey) {
      // We passed the ordered place of entry.
      return NULL; 
      
    } else {
      f = f->next;
      
    }
  }
  return NULL;
}
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
/* 
   gcc -g3 -lpthread -lrt -Wall -DLINUX_OS -DIDMAP_UNIT_TEST -pg -I ../utils ../utils/ownutils.c ../utils/owndebug.c idmap.c
   ./a.out
   valgrind -v ./a.out
*/
//*****************************************************************************

#ifdef IDMAP_UNIT_TEST
#include "ownutils.h"
int main(int argc, char *argv[])
{
  int i;
  TIDMap idm;
  unsigned int bins = 3;
  unsigned int dataelements = 10;
  ownTime_ms_t btime;
  ownTime_ms_delta_t since;
  float tperentry;

  if (argc > 1) {
    dataelements = atoi(argv[1]);
  }
  if (argc > 2) {
    bins = atoi(argv[2]);
  }


  btime = ownTime_get_ms();
  printf("Init IDMap with %u bins\n", bins);
  idMapInit(&idm, bins);
  printf("... Completed, in %u milliseconds\n", ownTime_get_ms_since(btime));



  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    idMapAddEntry(&idm, i, (void*)i);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Query %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    const TIDMapEntry *e = idMapGetEntry(&idm, i);
    assert(e != NULL);
    assert(e->entry == (void*)i);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);

  

  btime = ownTime_get_ms();
  printf("Delete %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    assert( idMapDeleteEntry(&idm, i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);



  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    assert( idMapAddEntry(&idm, i, (void*)i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);



  btime = ownTime_get_ms();
  printf("Query %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    const TIDMapEntry *e = idMapGetEntry(&idm, i);
    assert(e != NULL);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Delete %u entries in reverse order\n", dataelements);
  for(i=dataelements-1; i >= 0; --i) {
    assert( idMapDeleteEntry(&idm, i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    assert( idMapAddEntry(&idm, i, (void*)i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);

  btime = ownTime_get_ms();
  printf("Iterating %u entries...\n", dataelements);
  int n = 0;
  TIDMapEntryIterator ei;
  idMapGetNextEntryIterator(&idm, &ei);
  const TIDMapEntry *e;

  do {
    e = idMapGetNextEntry(&idm, &ei);
    if (e) {
      n++;
      if (argc == 4) printf("%u, ", e->nodeID);
    }
  } while (e);
  if (argc == 4) printf("\n");
  assert( n == dataelements );
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);




  btime = ownTime_get_ms();
  printf("calling idMapDeinit, with %u entries still in table...\n", dataelements);
  idMapDeinit(&idm);
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %u milliseconds. (%.2fus / entry)\n", since, tperentry);

  return 0;
}
#endif
//*****************************************************************************

